package cn.xaut.剑指offer.m01;

import java.util.Stack;

public class demo02 {
    
    // 206. 反转链表 1  超出时间限制
    public ListNode reverseList(ListNode head) {

        Stack<ListNode> stack = new Stack<>();
        ListNode p = head;
        while (p != null) {
            stack.add(p);
        }
        
        ListNode res = null;
        while (!stack.isEmpty()) {
            res = stack.pop();
            res = res.next;
        }
        
        return res;
    }


    // 反转链表（迭代）
    public ListNode reverseList2(ListNode head) {

        ListNode prev = null, cur = head;
        while (cur != null) {
            
            ListNode next = cur.next;
            cur.next = prev;
            prev = cur;
            cur = next;
        }
        return prev;
    }



    // 反转链表（递归）
    public ListNode reverseList3(ListNode head) {

        if (head == null || head.next == null) 
            return head;

        ListNode newHead = reverseList3(head.next);
        head.next.next = head;
        head.next = null;
        return newHead;
    }
}
